import typing

# 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径，路径可以从任何一格开始
# 每一步可以在矩阵中向左，右，上，下移动一格，如果一条路径经过了矩阵中的某乙格，那么该路径不能再次进入该格子

def has_path(matrix, s):

    if len(matrix)<=0 or len(matrix[0]) <= 0:
        return False

    visited = [[0 for i in j] for j in matrix ]

    path_length = 0

    rows, cols = len(matrix), len(matrix[0])

    for row in range(rows):
        for col in range(cols):
            if has_path_core(matrix, rows, cols, row, col, s, path_length, visited):
                return True

    return False




def has_path_core(matrix, rows, cols, row, col, s, path_length, visited):
    if len(s) == path_length:
        return True

    haspath = False
    if row>=0 and row < rows and col >= 0 and col < cols and matrix[row][col] == s[path_length] and not visited[row][col] :
        path_length += 1
        visited[row][col] = 1
        haspath = has_path_core(matrix, rows, cols, row, col-1, s, path_length, visited) or \
            has_path_core(matrix, rows, cols, row, col+1, s, path_length=path_length, visited=visited) or \
            has_path_core(matrix, rows, cols, row-1, col, s, path_length, visited) or\
            has_path_core(matrix, rows, cols, row+1, col, s, path_length, visited)
        if not haspath:
            path_length -= 1
            visited[row][col] = 0

    return haspath


if __name__ == '__main__':
    a = [list('abtg'), list('cfcs'), list('jdeh')]
    s = 'bfce'


    print(has_path(a, s))
